package com.yanceysong.codetop.s61_s70;

import java.util.concurrent.ThreadLocalRandom;


public class S66_Mid_470_用_Rand7_实现_Rand10 {
    // 统计 rand7 调用次数，用于效率评估
    private int rand7CallCounter = 0;

    /**
     * .用 rand7() 构造均匀分布的 rand10()。
     * .<p>
     * .题目: <a href="https://leetcode.cn/problems/implement-rand10-using-rand7/description/">470. 用 Rand7() 实现 Rand10()</a>
     * .<p>
     * .给定方法 rand7 能生成 [1,7] 范围内的均匀随机整数，请实现方法 rand10 生成 [1,10] 范围内的均匀随机整数。
     * .只能调用 rand7()，不能使用其它随机源。任何返回 1..10 的数字概率必须完全相等。
     * .<p>
     * .核心标签：数学 / 拒绝采样（Rejection Sampling）/ 概率 / 随机数 / 熵再利用
     * .<p>
     * .示例（伪运行，没有真实输入输出格式）：
     * .调用 10 次 rand10() 可能得到： [3, 8, 1, 10, 5, 5, 2, 9, 4, 6]
     * .每个位置独立且 1..10 概率均为 1/10。
     * .<p>
     * .核心步骤：
     * .1. 使用两次 rand7() 生成一个均匀整数 v ∈ [1,49]，公式 v = (rand7() - 1) * 7 + rand7()。
     * .2. 若 v > 10 则丢弃并重新生成，直到 v ∈ [1,10]。
     * .3. 返回 v，因 {1..10} 是全集 {1..49} 的均匀子集 => 分布仍保持均匀。
     * .<p>
     * .正确性：全集中每个数概率均为 1/49，条件限制到子集 {1..10} 后仍等概率，各值概率 = (1/49) / (10/49) = 1/10。
     * .<p>
     * .效率分析：
     * .- 接受概率 = 10/49 ≈ 0.2041
     * .- 期望循环轮数 = 49/10 ≈ 4.9
     * .- 每轮使用 2 次 rand7() => 期望调用 rand7() 次数 ≈ 9.8
     * .相比经典实现（接受前 40 个再取模，期望 ≈ 2.45 次调用）效率低 ~4 倍；相比优化多层回收版本（≈2.0~2.1）更低。
     * .<p>
     * .ASCII 位置图（✓ 表示被接受的格子；× 表示被拒绝）：
     * . 1  2  3  4  5  6  7    ✓ ✓ ✓ ✓ ✓ ✓ ✓
     * . 8  9 10 11 12 13 14    ✓ ✓ ✓ ×  ×  ×  ×
     * .15 16 17 18 19 20 21    ×  ×  ×  ×  ×  ×  ×
     * .22 23 24 25 26 27 28    ×  ×  ×  ×  ×  ×  ×
     * .29 30 31 32 33 34 35    ×  ×  ×  ×  ×  ×  ×
     * .36 37 38 39 40 41 42    ×  ×  ×  ×  ×  ×  ×
     * .43 44 45 46 47 48 49    ×  ×  ×  ×  ×  ×  ×
     * .<p>
     * .优缺点：
     * .+ 实现非常直观，易理解。
     * .- 丢弃比例过高（约 79.6%），效率较差，不推荐在真实生产或高性能场景使用。
     * .<p>
     * .建议：学习用途可以保留；实际提交题目可选用“接受 ≤40 后取模”的版本或多层回收的优化版本 rand10Optimized()。
     */
    public int rand10() {
        // 初次生成一个 1..49 的均匀随机数
        int num = (rand7() - 1) * 7 + rand7();
        // 若不在目标区间 1..10 内则重试（拒绝采样）
        while (num > 10) {
            num = (rand7() - 1) * 7 + rand7();
        }
        // 直接返回，已保证均匀性
        return num;
    }


    /**
     * ..多层再利用版本：对被拒绝区的随机性分层回收，降低期望调用次数。
     * ..@return 均匀的 1..10 随机整数
     */
    public int rand10Optimized() {
        while (true) {
            // 第一层：构造 49
            int firstStageVal = (rand7() - 1) * 7 + rand7(); // ∈[1,49]
            if (firstStageVal <= 40) { // 直接可用
                return 1 + (firstStageVal - 1) % 10;
            }
            // 第二层：利用 41..49 的 9 个数扩展到 63
            int secondStageVal = (firstStageVal - 40 - 1) * 7 + rand7(); // (firstStageVal-40)∈[1,9] -> secondStageVal ∈[1,63]
            if (secondStageVal <= 60) { // 前 60 可整除 10
                return 1 + (secondStageVal - 1) % 10;
            }
            // 第三层：利用 61..63 的 3 个数扩展到 21
            int thirdStageVal = (secondStageVal - 60 - 1) * 7 + rand7(); // (secondStageVal-60)∈[1,3] -> thirdStageVal ∈[1,21]
            if (thirdStageVal <= 20) { // 前 20 可整除 10
                return 1 + (thirdStageVal - 1) % 10;
            }
            // 剩余一个数 thirdStageVal=21 -> 回到最外层再次开始
        }
    }

    /**
     * ..模拟 rand7(): 返回 [1,7] 的均匀整数。这里同时统计调用次数用于效率分析。
     */
    private int rand7() {
        rand7CallCounter++; // 统计一次调用
        return ThreadLocalRandom.current().nextInt(1, 8); // [1,8) => 1..7
    }

    /**
     * ..获取并重置 rand7 调用计数器（原子读取+清零）。
     * ..@return 重置前的调用次数
     */
    private int getAndResetRand7Counter() {
        int prev = rand7CallCounter;
        rand7CallCounter = 0;
        return prev;
    }

    /**
     * ..频率统计：执行大量采样统计出现频率，用于验证均匀性。
     * ..@param generator 提供随机数的函数式接口实现
     * ..@param sampleCount 采样次数
     * ..@return 每个值出现次数数组，下标 0..9 对应数字 1..10
     */
    private int[] sampleFrequency(IntGenerator generator, int sampleCount) {
        int[] freq = new int[10];
        for (int i = 0; i < sampleCount; i++) {
            int val = generator.next();
            if (val < 1 || val > 10) {
                throw new IllegalStateException("生成值越界: " + val);
            }
            freq[val - 1]++;
        }
        return freq;
    }

    /**
     * ..评估效率：统计多次生成 rand10 时平均调用 rand7 的次数。
     * ..@param generator 随机生成函数
     * ..@param sampleCount 采样次数
     * ..@return 平均调用次数
     */
    private double evaluateEfficiency(IntGenerator generator, int sampleCount) {
        getAndResetRand7Counter(); // 清零计数器
        for (int i = 0; i < sampleCount; i++) {
            generator.next();
        }
        int totalCalls = getAndResetRand7Counter();
        return totalCalls * 1.0 / sampleCount;
    }

    /**
     * ..函数式接口：返回一个 int 随机值
     */
    @FunctionalInterface
    private interface IntGenerator {
        int next();
    }

    public static void main(String[] args) {
        S66_Mid_470_用_Rand7_实现_Rand10 solution = new S66_Mid_470_用_Rand7_实现_Rand10();
        System.out.println("=== Rand10 随机数生成测试开始 ===");

        // 1. 基本多次输出观察区间
        System.out.println("\n--- 基础版随机输出 20 次 ---");
        for (int i = 0; i < 20; i++) {
            System.out.print(solution.rand10() + (i == 19 ? "\n" : ", "));
        }
        System.out.println("\n--- 优化版随机输出 20 次 ---");
        for (int i = 0; i < 20; i++) {
            System.out.print(solution.rand10Optimized() + (i == 19 ? "\n" : ", "));
        }

        // 2. 频率分布测试：大样本检测近似均匀性
        int freqSamples = 100_000; // 可调；样本越大越接近均匀
        System.out.println("\n--- 频率统计，样本量 = " + freqSamples + " (基础版) ---");
        int[] freqBasic = solution.sampleFrequency(solution::rand10, freqSamples);
        printFrequency(freqBasic);
        System.out.println("\n--- 频率统计，样本量 = " + freqSamples + " (优化版) ---");
        int[] freqOptimized = solution.sampleFrequency(solution::rand10Optimized, freqSamples);
        printFrequency(freqOptimized);

        // 3. 均匀性简单断言（允许 5% 相对误差）
        double tolerance = 0.05; // 5%
        assertUniform(freqBasic, freqSamples, tolerance, "基础版");
        assertUniform(freqOptimized, freqSamples, tolerance, "优化版");

        // 4. 效率评估：测平均 rand7 调用次数
        int efficiencySamples = 50_000; // 较大样本以平滑波动
        double avgBasic = solution.evaluateEfficiency(solution::rand10, efficiencySamples);
        double avgOptimized = solution.evaluateEfficiency(solution::rand10Optimized, efficiencySamples);
        System.out.println("\n--- 效率评估 (平均 rand7 调用次数) ---");
        System.out.printf("基础版: %.4f (理论≈2.45)\n", avgBasic);
        System.out.printf("优化版: %.4f (理论≈2.0~2.1)\n", avgOptimized);
        System.out.println("提升比 (基础/优化) ≈ " + String.format("%.3f", avgBasic / avgOptimized));

        // 5. 极小样本边界测试（快速 sanity）
        System.out.println("\n--- 边界测试：单次调用 ---");
        int singleBasic = solution.rand10();
        int singleOptimized = solution.rand10Optimized();
        if (singleBasic < 1 || singleBasic > 10 || singleOptimized < 1 || singleOptimized > 10) {
            throw new AssertionError("边界测试失败：结果越界");
        }
        System.out.println("单次基础版结果=" + singleBasic + ", 单次优化版结果=" + singleOptimized + " (均在1..10内) ");

        System.out.println("\n✓ 所有测试完成 (若未触发断言则认为通过)\n");
    }

    /**
     * ..打印频率与相对比例
     */
    private static void printFrequency(int[] freq) {
        int total = 0;
        for (int f : freq) total += f;
        for (int i = 0; i < freq.length; i++) {
            double ratio = freq[i] * 1.0 / total;
            // 修正百分比显示：ratio * .100
            System.out.printf("值 %2d 出现 %6d 次，占比 %.4f%%\n", i + 1, freq[i], ratio * .100);
        }
    }

    /**
     * ..简单均匀性断言：每个值的频率应接近 total/10
     */
    private static void assertUniform(int[] freq, int total, double tolerance, String label) {
        double expected = total / 10.0;
        for (int i = 0; i < freq.length; i++) {
            double deviation = Math.abs(freq[i] - expected) / expected;
            // 修正偏差百分比显示：deviation * .100
            if (deviation > tolerance) {
                throw new AssertionError(String.format("[%s] 数值 %d 频率偏差过大: 实际=%d 期望≈%.2f 偏差=%.2f%%", label, i + 1, freq[i], expected, deviation * .100));
            }
        }
        System.out.println("均匀性断言通过: " + label);
    }
}
